package trees;

/**
 * @description a generic version of BSTree.java
 *
 * @param <T>
 */
class BSTreeG<T extends Comparable<T>> {
    private static class Node<T> {
        private T item;
        private Node<T> left;
        private Node<T> right;

        public Node(T item) {
            this.item = item;
            left = null;
            right = null;
        }
    }

    private Node<T> root;

    public T find(T x) {
        return find(root, x);
    }

    private T find(Node<T> t, T x) {
        while (t != null)
            if (x.compareTo(t.item) < 0)
                t = t.left;
            else if (x.compareTo(t.item) > 0)
                t = t.right;
            else
                return t.item;
        return null;
    }

    public T findMin() {
        return findMin(root);
    }

    private T findMin(Node<T> t) {
        if (t != null) {
            while (t.left != null)
                t = t.left;
            return t.item;
        }
        return null;
    }

    public T findMax() {
        return findMax(root);
    }

    private T findMax(Node<T> t) {
        if (t != null) {
            while (t.right != null)
                t = t.right;
            return t.item;
        }
        return null;
    }

    public void insert(T x) {
        root = insert(root, x);
    }

    private Node<T> insert(Node<T> t, T x) {
        if (t == null)
            t = new Node<T>(x);
        else if (x.compareTo(t.item) < 0)
            t.left = insert(t.left, x);
        else if (x.compareTo(t.item) > 0)
            t.right = insert(t.right, x);
        return t;
    }

    public void remove(T x) {
        root = remove(root, x);
    }

    private Node<T> remove(Node<T> t, T x) {
        if (t != null) {
            if (x.compareTo(t.item) < 0)
                t.left = remove(t.left, x);
            else if (x.compareTo(t.item) > 0)
                t.right = remove(t.right, x);
            else if (t.left == null)
                t = t.right;
            else if (t.right == null)
                t = t.left;
            else {
                t.item = findMin(t.right);
                t.right = remove(t.right, t.item);
            }
        }
        return t;
    }

    private void indent(int depth, Node<T> node) {
        for (int i = 0; i < depth; i++)
            System.out.print("   ");
        System.out.println(node.item);
    }

    private void inorder() {
        inorder(root, 0);
    }

    private void inorder(Node<T> node, int depth) {
        if (node != null) {
            inorder(node.right, depth + 1);
            indent(depth, node);
            inorder(node.left, depth + 1);
        }
    }

    public static BSTreeG<String> makeTree(String[] items) {
        BSTreeG<String> tree = new BSTreeG<String>();
        for (int i = 0; i < items.length; i++)
            tree.insert(items[i]);
        return tree;
    }

    public static void testTree(BSTreeG tree) {
        System.out.println("INORDER");
        System.out.println();
        tree.inorder();
        System.out.println();
        System.out.println("find min: " + tree.findMin());
        System.out.println("find max: " + tree.findMax());
        System.out.println("find E: " + tree.find("E"));
        tree.remove("D");
        System.out.println("INORDER");
        System.out.println();
        tree.inorder();
        System.out.println();
    }

    public static void main(String[] args) {
        String[] rand = { "D", "H", "C", "A", "F", "E", "G", "B" };
        BSTreeG<String> tree = makeTree(rand);
        testTree(tree);

        String[] alpha = { "A", "B", "C", "D", "E", "F", "G", "H" };
        tree = makeTree(alpha);
        testTree(tree);
    }
}